//https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
//思想1:hash表应用！！！；insert 实际就是在去重操作；
//思想2:hash表独创！！

#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> num_set;
        for (const int& num : nums) {
            num_set.insert(num);
        }

        int longestStreak = 0;

        for (const int& num : num_set) {
            if (!num_set.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.count(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;           
    }
};


class Solution2 {
public:
    int longestConsecutive(vector<int>& nums) {
        std::set<int> m;
        std::vector<int>v;
        for(const auto& i:nums) {
            m.insert(i);
        }
        int largest_len=0;
        int pre = INT32_MAX;
        int cur_len=0;
        for(set<int>::iterator iter = m.begin(); iter != m.end(); ++iter){
            if((*iter)-1 == pre) {
                cur_len+=1;
                pre=*iter;
            }else{
                cur_len=1;
                pre=*iter;
            }
            largest_len=std::max(largest_len,cur_len);
        }
        return largest_len;
    }
};